﻿#include <iostream>
#include <list>
#include <forward_list>
#include <deque>
#include <stack>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <functional>
#include <unordered_map>
#include <bitset>


bool myCompare(const std::string& a, const std::string& b) {
	return a < b;
}




int main()
{

	/*
	<list> 是 C++ 标准模板库（STL）中的一个序列容器，它允许在容器的任意位置快速插入和删除元素。
	与数组或向量（<vector>）不同，<list> 不需要在创建时指定大小，并且可以在任何位置添加或
	删除元素，而不需要重新分配内存。

	以下是 <list> 容器的一些基本操作：
	包含头文件：#include <list>
	声明列表：std::list<T> mylist;，其中 T 是存储在列表中的元素类型。
	插入元素：mylist.push_back(value);
	删除元素：mylist.pop_back(); 或 mylist.erase(iterator);
	访问元素：mylist.front(); 和 mylist.back();
	遍历列表：使用迭代器 for (auto it = mylist.begin(); it != mylist.end(); ++it)
	*/


	std::list<int> ns{ 1,2,3,4,5,6,7,8,9,10 };
	ns.push_back(1);
	ns.pop_back();
	int font = ns.front();
	int bk = ns.back();

	//遍历元素
	for (std::list<int>::iterator it = ns.begin(); it != ns.end(); ++it)
	{
		std::cout << *it << ",";
	}
	std::cout << "\n";


	// 输出链表内容
	std::cout << "List elements: ";
	for (const auto& elem : ns) {
		std::cout << elem << " ";
	}
	std::cout << std::endl;


	auto it = ns.begin();
	std::advance(it, 2);          // 移动迭代器到第3个元素（值为3）
	ns.insert(it, 10);           // 在第3个元素前插入10
	ns.erase(it);                // 删除第3个元素


	ns.sort();                    // 排序
	ns.unique();                  // 删除相邻重复元素


	std::list<int> lst1 = { 1, 3, 5, 7 };
	std::list<int> lst2 = { 2, 4, 6, 8 };
	lst1.merge(lst2);              // 合并两个已排序的链表
	lst1.reverse();                // 反转链表



	// 输出链表内容
	std::cout << "Merged and reversed list: ";
	for (const auto& elem : lst1) {
		std::cout << elem << " ";
	}
	std::cout << std::endl;




	//单向链表：只能从前往后遍历，不能反向遍历
	std::forward_list<int> f;
	f.push_front(10);

	//遍历
	for (auto it = f.begin(); it != f.end(); ++it)
	{
		std::cout << *it << ",";
	}
	std::cout << std::endl;


	//双端队列
	std::deque<int> que;
	que.push_back(1);
	que.push_front(0);

	//访问元素
	int qu = que[0];

	//删除元素
	que.pop_front();
	que.pop_back();

	//元素大小
	que.size();




	/*
	<stack> 是一个后进先出（LIFO，Last In First Out）的数据结构。
	这种数据结构非常适合于需要"最后添加的元素最先被移除"的场景。

	<stack> 容器适配器提供了一个栈的接口，它基于其他容器（如 deque 或 vector）来实现。
	栈的元素是线性排列的，但只允许在一端（栈顶）进行添加和移除操作。
	*/
	std::stack<int> st;
	st.push(0);
	int top = st.top(); //访问栈顶元素
	st.pop();//移除栈顶元素
	int size = st.size();

	//<stack> 不提供直接访问栈中元素的方法，只能通过 top() 访问栈顶元素。
	//尝试在空栈上调用 top() 或 pop() 将导致未定义行为。





	/*
	队列是一种先进先出（FIFO, First In First Out）的数据结构，它允许在一端添加元素（称为队尾），并在另一端移除元素（称为队首）。
	队列是一种线性数据结构，它遵循以下规则：
	元素只能从队尾添加。
	元素只能从队首移除。
	*/
	// 创建一个整数队列
	std::queue<int> q;

	// 向队列中添加元素
	q.push(10);
	q.push(20);
	q.push(30);

	// 打印队列中的元素数量
	std::cout << "队列中的元素数量: " << q.size() << std::endl;

	// 打印队首元素
	std::cout << "队首元素: " << q.front() << std::endl;

	// 打印队尾元素
	std::cout << "队尾元素: " << q.back() << std::endl;

	// 移除队首元素
	q.pop();
	std::cout << "移除队首元素后，队首元素: " << q.front() << std::endl;

	// 再次打印队列中的元素数量
	std::cout << "队列中的元素数量: " << q.size() << std::endl;




	//优先队列是一种特殊的队列，它允许我们快速访问队列中具有最高（或最低）优先级的元素。
	// 创建一个整型优先队列
	std::priority_queue<int> pq;

	// 向优先队列中添加元素
	pq.push(30);
	pq.push(10);
	pq.push(50);
	pq.push(20);

	// 输出队列中的元素
	std::cout << "队列中的元素：" << std::endl;
	while (!pq.empty()) {
		std::cout << pq.top() << std::endl;
		pq.pop();
	}




	/*
	<set> 是一个关联容器，它存储了一组唯一的元素，并按照一定的顺序进行排序。
	<set> 提供了高效的元素查找、插入和删除操作。它是基于红黑树实现的，因此具有对数时间复杂度的查找、插入和删除性能。
	<set> 容器中存储的元素类型必须满足以下条件：
	元素类型必须可以比较大小。
	元素类型必须可以被复制和赋值。
	*/

	std::set<int> mySet;
	mySet.insert(1);//插入
	mySet.erase(1); //删除
	auto fd = mySet.find(1); //查找
	size = mySet.size(); //元素的数量
	bool isemp = mySet.empty(); //容器是否为空





	/*
	<unordered_set> 是标准模板库（STL）的一部分，提供了一种基于哈希表的容器，用于存储唯一的元素集合。
	与 set 不同，unordered_set 不保证元素的排序，但通常提供更快的查找、插入和删除操作。
	*/
	std::unordered_set<int> uset;
	uset.insert(1);//插入
	uset.erase(1); //删除
	auto fd2 = uset.find(1); //查找
	size = uset.size(); //元素的数量
	isemp = uset.empty(); //容器是否为空




	//map 容器中的元素是按照键的顺序自动排序的，这使得它非常适合需要快速查找和有序数据的场景。
	/*定义和特性
	键值对：map 存储的是键值对，其中每个键都是唯一的。
	排序：map 中的元素按照键的顺序自动排序，通常是升序。
	唯一性：每个键在 map 中只能出现一次。
	双向迭代器：map 提供了双向迭代器，可以向前和向后遍历元素。*/

	std::map<std::string, int> mp;
	mp["A"] = 1;
	mp["B"] = 2;
	mp["C"] = 3;

	//遍历map
	for (auto m = mp.begin(); m != mp.end(); ++m)
	{
		std::cout << m->first << "=" << m->second << "\n";
	}

	//检查键是否存在:
	if (mp.find("A") != mp.end())
	{
		// 键存在

	}
	else
	{
		// 键不存在	
	}

	mp.erase("A"); //删除
	mp.clear(); //清空
	size = mp.size(); //大小
	mp.empty(); //是否为空
	mp.count("A"); // key 是否存在（返回 0 或 1）

	//自定义排序，默认升序排序，可以用 std::greater 或自定义比较函数：
	std::map<int, std::string, std::greater<int>> m;  // 降序
	std::map<std::string, int, std::function<bool(const std::string&, const std::string&)>> myMap(myCompare);





	/*
	unordered_map 不保证元素的排序，但通常提供更快的查找速度。
	unordered_map 是一个关联容器，它存储了键值对（key - value pairs），
	其中每个键（key）都是唯一的。unordered_map 使用哈希表来存储元素，
	这使得它在查找、插入和删除操作中具有平均常数时间复杂度。
	*/
	// 创建一个 unordered_map，键为 int，值为 string
	std::unordered_map<int, std::string> myMap2;

	// 插入一些键值对
	myMap2[1] = "one";
	myMap2[2] = "two";
	myMap2[3] = "three";

	// 打印所有元素
	for (const auto& pair : myMap2) {
		std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
	}

	// 访问特定键的值
	std::cout << "Value for key 2: " << myMap2[2] << std::endl;

	// 删除键为1的元素
	myMap2.erase(1);

	// 再次打印所有元素
	std::cout << "After erasing key 1:" << std::endl;
	for (const auto& pair : myMap2) {
		std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
	}





	/*
	位集合是一个由位（bit）组成的数组，每个位可以是 0 或 1。
	<bitset> 提供了一种高效的方式来存储和操作二进制数据，特别适合需要位级操作的场景，如标志位管理、位掩码操作等。
	*/
	std::bitset<8> b("11001010"); // 从字符串初始化
	std::cout << "Initial bitset: " << b << std::endl;

	// 访问特定位置的位
	std::cout << "Bit at position 3: " << b[3] << std::endl;

	// 修改位
	b[3] = 1;
	std::cout << "Modified bitset: " << b << std::endl;

	// 翻转位
	b.flip();
	std::cout << "Flipped bitset: " << b << std::endl;


	std::bitset<8> bits1("10101010");
	std::bitset<8> bits2("11110000");

	std::bitset<8> result_and = bits1 & bits2;  // 按位与：10100000
	std::bitset<8> result_or = bits1 | bits2;   // 按位或：11111010
	std::bitset<8> result_xor = bits1 ^ bits2;  // 按位异或：01011010
	std::bitset<8> result_not = ~bits1;         // 按位取反：01010101
}
